package leetcode_数组;

import java.util.List;

/**
 * 单词拆分
 * <p>算法: 字典树 + 记忆化搜索</p>
 *
 * @author yezh
 * @date 2023/8/10 11:31
 */
public class _139 {

    public boolean wordBreak(String s, List<String> wordDict) {
        Node node = new Node();
        for (String word : wordDict) node.add(word);
        // -1 表示不能拆分, 1 表示可以拆分
        int[] dp = new int[s.length() + 1];
        // 以 i 为开始的字符能不能被拆分
        return wordBreak(0, dp, s, node);
    }

    boolean wordBreak(int i, int[] dp, String s, Node node) {
        if (i == s.length() || dp[i] == 1) return true;
        // 剪枝
        if (dp[i] == -1) return false;
        Node cur = node;
        for (; i < s.length(); i++) {
            cur = cur.children[s.charAt(i) - 'a'];
            if (cur == null) return false;
            if (cur.end) {
                if (wordBreak(i + 1, dp, s, node)) {
                    dp[i + 1] = 1;
                    return true;
                } else {
                    dp[i + 1] = -1;
                }
            }
        }
        return false;
    }

    private static class Node {
        Node[] children;
        boolean end;

        public Node() {
            children = new Node[26];
            end = false;
        }

        public void add(String s) {
            Node cur = this;
            for (char c : s.toCharArray()) {
                if (cur.children[c - 'a'] == null) cur.children[c - 'a'] = new Node();
                cur = cur.children[c - 'a'];
            }
            cur.end = true;
        }
    }

}
